#
# @lc app=leetcode.cn id=463 lang=python3
#
# [463] 岛屿的周长
#
from typing import List


# @lc code=start
class Solution:
    def islandPerimeter1(self, grid: List[List[int]]) -> int:
        hLen = len(grid[0])
        vLen = len(grid)
        island = {}
        v = 0
        while v < vLen:
            h = 0
            flag = 0
            while h < hLen:
                if grid[v][h] == 1:
                    flag = 1
                    break
                h += 1
            if flag == 1:
                break
            v += 1
        if v == vLen and h == hLen:
            return 0

        def calIsland(v, h):
            c = 4
            for k in (-1, 1):
                if -1 < v + k < vLen and grid[v + k][h] == 1:
                    c -= 1
                if -1 < h + k < hLen and grid[v][h + k] == 1:
                    c -= 1
            island[(v, h)] = c
            for k in (-1, 1):
                if (v + k, h) not in island and -1 < v + k < vLen and grid[
                        v + k][h] == 1:
                    calIsland(v + k, h)
                if (v, h + k) not in island and -1 < h + k < hLen and grid[v][
                        h + k] == 1:
                    calIsland(v, h + k)

        calIsland(v, h)
        ans = 0
        for val in island.values():
            ans += val
        return ans

    def islandPerimeter(self, grid: List[List[int]]) -> int:
        island = {}
        vLen = len(grid)
        hLen = len(grid[0])
        v = 0
        while v < vLen:
            h = 0
            while h < hLen:
                if grid[v][h] == 1:
                    island[(v, h)] = 4
                    for i in (-1, 1):
                        if -1 < v + i < vLen and grid[v + i][h] == 1:
                            island[(v, h)] -= 1
                        if -1 < h + i < hLen and grid[v][h + i] == 1:
                            island[(v, h)] -= 1
                h += 1
            v += 1
        ans = 0
        for val in island.values():
            ans += val
        return ans


if __name__ == "__main__":
    s = Solution()
    print(
        s.islandPerimeter([[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0],
                           [1, 1, 0, 0]]), 16)
    print(s.islandPerimeter([[1, 0]]), 4)
# @lc code=end
